import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return just(root,"");
    }
    public String just(TreeNode root,String str){
        if(root==null){
            str=str+"tmp,";
        }else{
            str+= str.valueOf(root.val)+",";
            str=just(root.left,str);
            str=just(root.right,str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split(",");
        List<String> list=new LinkedList<>(Arrays.asList(str));
        return back(list);
    }
    public TreeNode back(List<String> list){
        if(list.get(0).equals("tmp")){
            list.remove(0);
            return null;
        }
        TreeNode root=new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left=back(list);
        root.right=back(list);
        return root;
    }
}
















public class project {
    List<List<String>> list=new ArrayList<>();
    int sum=0;
    public int totalNQueens(int n) {
        char[][] ch=new char[n][n];
        for(char[] c:ch){
            Arrays.fill(c,'.');
        }
        back(ch,0);
        return this.sum;
    }
    public void back(char[][] ch,int len){
        if(len==ch.length){
            this.sum++;
            return;
        }
        int n=ch[len].length;
        for(int size=0;size<n;size++){
            if(!find(ch,len,size)){
                continue;
            }
            ch[len][size]='Q';
            back(ch,len+1);
            ch[len][size]='.';
        }
    }
    public boolean find(char[][] ch,int row,int col){
        int n=ch.length;
        for(int i=0;i<n;i++){
            if(ch[i][col]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(ch[i][j]=='Q'){
                return false;
            }
        }

        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(ch[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }













    public int smallestRangeI(int[] nums, int k) {
        int len=nums.length;
        int max=nums[0];
        int min=nums[0];
        for(int i=1;i<len;i++){
            min=Math.min(min,nums[i]);
            max=Math.max(max,nums[i]);
        }
        int sum=max-min;
        return sum<=k*2?0:sum-k*2;
    }
}
